LeetCode——合并区间

NO.56 合并区间 中等

思路一：排序 将所有区间按照左边界大小进行非递减排序。

什么样的区间是重叠的需要合并？

[1,3]、[2,6] 第1个区间的右边界大于下一个区间的左边界即发生重叠。

需要合并成[第一个区间的左边界,max(第一个区间的右边界,第二个区间的右边界)]这个区间加入结果集。

public int[][] merge(int[][] intervals) {
    List<int[]> res=new ArrayList<>();
    if (intervals==null||intervals.length==0)return res.toArray(new int[0][]);
    //每个区间按照区间左边界升序排序
    Arrays.sort(intervals, (o1,o2)->o1[0]-o2[0]);
    //遍历每个区间
    for (int pre = 0; pre < intervals.length; pre++) {
        //记录当前区间的左右边界值
        int left=intervals[pre][0],right=intervals[pre][1];
        //如果当前区间的右边界大于下一个区间的左边界，即发生重叠
        while (pre<intervals.length-1&&right>=intervals[pre+1][0]){
            right=Math.max(right,intervals[pre+1][1]);
            pre++;
        }
        res.add(new int[]{left,right});
    }
    return res.toArray(new int[0][]);
}

时间复杂度：O(n*logn) 区间数组只需要遍历一次，主要是排序的时间复杂度。

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github